package leetcode;

/*
874. 模拟行走机器人
机器人在一个无限大小的网格上行走，从点 (0, 0) 处开始出发，面向北方。该机器人可以接收以下三种类型的命令：
-2：向左转 90 度
-1：向右转 90 度
1 <= x <= 9：向前移动 x 个单位长度
在网格上有一些格子被视为障碍物。
第 i 个障碍物位于网格点  (obstacles[i][0], obstacles[i][1])
机器人无法走到障碍物上，它将会停留在障碍物的前一个网格方块上，但仍然可以继续该路线的其余部分。
返回从原点到机器人所有经过的路径点（坐标为整数）的最大欧式距离的平方。
示例 1：
输入: commands = [4,-1,3], obstacles = []
输出: 25
解释: 机器人将会到达 (3, 4)
示例 2：
输入: commands = [4,-1,4,-2,4], obstacles = [[2,4]]
输出: 65
解释: 机器人在左转走到 (1, 8) 之前将被困在 (1, 4) 处
提示：
0 <= commands.length <= 10000
0 <= obstacles.length <= 10000
-30000 <= obstacle[i][0] <= 30000
-30000 <= obstacle[i][1] <= 30000
答案保证小于 2 ^ 31
*/

import java.util.HashSet;
import java.util.Set;

public class problems_874 {
    public static void main(String[] args) {
        System.out.println(new Solution().robotSim(new int[]{
                1, 2, -2, 5, -1, -2, -1, 8, 3, -1, 9, 4, -2, 3, 2, 4, 3, 9, 2, -1, -1, -2, 1, 3, -2, 4, 1, 4, -1, 1, 9, -1, -2, 5, -1, 5, 5, -2, 6, 6, 7, 7, 2, 8, 9, -1, 7, 4, 6, 9, 9, 9, -1, 5, 1, 3, 3, -1, 5, 9, 7, 4, 8, -1, -2, 1, 3, 2, 9, 3, -1, -2, 8, 8, 7, 5, -2, 6, 8, 4, 6, 2, 7, 2, -1, 7, -2, 3, 3, 2, -2, 6, 9, 8, 1, -2, -1, 1, 4, 7
        }, new int[][]{
                {-57, -58}, {-72, 91}, {-55, 35}, {-20, 29}, {51, 70}, {-61, 88}, {-62, 99}, {52, 17}, {-75, -32}, {91, -22}, {54, 33}, {-45, -59}, {47, -48}, {53, -98}, {-91, 83}, {81, 12}, {-34, -90}, {-79, -82}, {-15, -86}, {-24, 66}, {-35, 35}, {3, 31}, {87, 93}, {2, -19}, {87, -93}, {24, -10}, {84, -53}, {86, 87}, {-88, -18}, {-51, 89}, {96, 66}, {-77, -94}, {-39, -1}, {89, 51}, {-23, -72}, {27, 24}, {53, -80}, {52, -33}, {32, 4}, {78, -55}, {-25, 18}, {-23, 47}, {79, -5}, {-23, -22}, {14, -25}, {-11, 69}, {63, 36}, {35, -99}, {-24, 82}, {-29, -98}, {-50, -70}, {72, 95}, {80, 80}, {-68, -40}, {65, 70}, {-92, 78}, {-45, -63}, {1, 34}, {81, 50}, {14, 91}, {-77, -54}, {13, -88}, {24, 37}, {-12, 59}, {-48, -62}, {57, -22}, {-8, 85}, {48, 71}, {12, 1}, {-20, 36}, {-32, -14}, {39, 46}, {-41, 75}, {13, -23}, {98, 10}, {-88, 64}, {50, 37}, {-95, -32}, {46, -91}, {10, 79}, {-11, 43}, {-94, 98}, {79, 42}, {51, 71}, {4, -30}, {2, 74}, {4, 10}, {61, 98}, {57, 98}, {46, 43}, {-16, 72}, {53, -69}, {54, -96}, {22, 0}, {-7, 92}, {-69, 80}, {68, -73}, {-24, -92}, {-21, 82}, {32, -1}, {-6, 16}, {15, -29}, {70, -66}, {-85, 80}, {50, -3}, {6, 13}, {-30, -98}, {-30, 59}, {-67, 40}, {17, 72}, {79, 82}, {89, -100}, {2, 79}, {-95, -46}, {17, 68}, {-46, 81}, {-5, -57}, {7, 58}, {-42, 68}, {19, -95}, {-17, -76}, {81, -86}, {79, 78}, {-82, -67}, {6, 0}, {35, -16}, {98, 83}, {-81, 100}, {-11, 46}, {-21, -38}, {-30, -41}, {86, 18}, {-68, 6}, {80, 75}, {-96, -44}, {-19, 66}, {21, 84}, {-56, -64}, {39, -15}, {0, 45}, {-81, -54}, {-66, -93}, {-4, 2}, {-42, -67}, {-15, -33}, {1, -32}, {-74, -24}, {7, 18}, {-62, 84}, {19, 61}, {39, 79}, {60, -98}, {-76, 45}, {58, -98}, {33, 26}, {-74, -95}, {22, 30}, {-68, -62}, {-59, 4}, {-62, 35}, {-78, 80}, {-82, 54}, {-42, 81}, {56, -15}, {32, -19}, {34, 93}, {57, -100}, {-1, -87}, {68, -26}, {18, 86}, {-55, -19}, {-68, -99}, {-9, 47}, {24, 94}, {92, 97}, {5, 67}, {97, -71}, {63, -57}, {-52, -14}, {-86, -78}, {-17, 92}, {-61, -83}, {-84, -10}, {20, 13}, {-68, -47}, {7, 28}, {66, 89}, {-41, -17}, {-14, -46}, {-72, -91}, {4, 52}, {-17, -59}, {-85, -46}, {-94, -23}, {-48, -3}, {-64, -37}, {2, 26}, {76, 88}, {-8, -46}, {-19, -68}
        }));
    }

    static class Solution {
        final Long MAX_LIMIT = 30000L; // 最大长度限制
        public int robotSim(int[] commands, int[][] obstacles) {
            //  初始方向为北，以顺时针方向依次定义： 北 0，东 1，南 2，西 3
            int direction = 0;
            // 定义数组，x轴或者y轴在每个方向前进一步走的距离，四个值分别对应北、东、南、西
            int[] dx = {0, 1, 0, -1};
            int[] dy = {1, 0, -1, 0};

            // 初始坐标
            int x = 0;
            int y = 0;
            // 最大欧式距离平方
            int max = 0;

            // 将障碍物坐标编码为hashcode存在hashSet中
            Set<Long> obstacleSet = new HashSet<>();
            for (int[] obstacle : obstacles) {
                long ox = (long) obstacle[0] + MAX_LIMIT;
                long oy = (long) obstacle[1] + MAX_LIMIT;
                obstacleSet.add((ox << 16) + oy);
            }

            for (int cmd : commands) {
                // 遍历每个指令
                if (cmd == -2) {
                    // 向左转，以顺时针方向加3取余
                    direction = (direction + 3) % 4;
                } else if (cmd == -1) {
                    // 向右转，以顺时针方向加1取余
                    direction = (direction + 1) % 4;
                } else {
                    // 行进
                    for (int i = 0; i < cmd; i++) {
                        int xx = x + dx[direction];
                        int yy = y + dy[direction];
                        long hashCode = (((long) xx + MAX_LIMIT) << 16) + ((long) yy + MAX_LIMIT);
                        if (!obstacleSet.contains(hashCode)) {
                            // 如果没有障碍，x轴/y轴走一步
                            x = xx;
                            y = yy;
                            max = Math.max(max, x * x + y * y);
                        }
                    }
                }
            }
            return max;
        }
    }


    // 以下错误
//    static class Solution {
//        public int robotSim(int[] commands, int[][] obstacles) {
//            Map<Integer, List<Integer>> map = new HashMap<>();
//            // 阻碍点保存
//            for (int i = 0; i < obstacles.length; i++) {
//                int[] obstacle = obstacles[i];
//                if (!map.containsKey(obstacle[0])) map.put(obstacle[0], new ArrayList<Integer>());
//                map.get(obstacle[0]).add(obstacle[1]);
//            }
//
//            // 位置点
//            int[] index = new int[]{0, 0};
//            // 方向
//            int direction = 1; // 方向表示 0北，1东，2南，3西
//            // 命令执行
//            for (int i = 0; i < commands.length; i++) {
//                int command = commands[i];
//
//                if (command == -2) {
//                    // -2：向左转 90 度
//                    direction = (direction - 1 + 4) % 4;
//                } else if (command == -1) {
//                    // -1：向右转 90 度
//                    direction = (direction + 1) % 4;
//                } else {
//                    // 移动处理
//                    index = move(index, direction, command, map);
//                }
//
//                System.out.println("("+index[0]+","+index[1]+")_" + direction + "_命令" + command);
//            }
//            // 返回值
//            return (int) (Math.pow(Math.abs(index[0]), 2) + Math.pow(Math.abs(index[1]), 2));
//        }
//        // 处理移动
//        private int[] move(int[] index, int direction, int command, Map<Integer, List<Integer>> mapObstacles) {
//            for (int i = 0; i < command; i++) {
//                // 坐标变换
//                int x = index[0]; // X轴
//                int y = index[1]; // Y轴
//                switch (direction){
//                    case 0: x++;break; // 北
//                    case 1: y++;break; // 东
//                    case 2: x--;break; // 南
//                    case 3: y--;break; // 西
//                }
//                // 判断是否遇到阻碍
//                if (mapObstacles.containsKey(x) && mapObstacles.get(x).contains(y)) {
//                    System.out.println("阻碍");
//                    break;
//                }
//
//                // 设置
//                index[0] = x;
//                index[1] = y;
//            }
//            return index;
//        }
//    }
}